package com.study.algorithm.basicalsort.imp;

import com.study.algorithm.basicalsort.BasicalSort;
import com.study.algorithm.utils.ListUtil;

import java.util.ArrayList;
import java.util.List;


/**
 * 归并排序
 * 原理：
 * 先拆分数据段，后合并数据段
 * 它是一种分治算法，就是先将完整的集合分化为多个小的集合
 * 采用分盘，分段等方式，先段内部排序，然后将有序的小段，
 * 在两两（或者更多）拼接成一个更大的有序段（二路归并）
 * 直至拼接完成最终的一个大的有序段，排序完成
 * 演示常规思路（采用伪分段，其实就是在源集合里直接操作，与其他算法保持一致，便于测试)
 * *（扩展：大数据算法可能就是由此演变而来的，顶部算法采用多路归并，底部算法，
 * *根据量级不同采用不同算法，
 * *其中的核心在于顶部算法数据拆分与合并时的策略）
 */

public class MergeSortImpl implements BasicalSort {
    @Override
    public List<Integer> basicalSort(List<Integer> originList) {

        int size = originList.size();
        List<Integer> destList = ListUtil.DeepClone(originList);
        if (size <= 1) {
            return destList;
        }

        mergeSort(destList, new Section(0, size - 1));
        return destList;
    }

    private void mergeSort(List<Integer> dataList, Section section) {
        if (!validateSectionIsSpilt(section)) {
            //分段只用唯一的一个点，即已经是有序的了
            section.setOrder(true);
            return;
        }

        int spiltPositionIndex = getSplitSectionIndex(section);
        int startIndex = section.getStartIndex();
        int endIndex = section.getEndIndex();
        Section leftSection = new Section(startIndex, spiltPositionIndex);
        Section rightSection = new Section(spiltPositionIndex + 1, endIndex);
        mergeSection(dataList, leftSection, rightSection);
        section.setOrder(true);
    }

    private void mergeSection(List<Integer> dataList, Section section1, Section section2) {
        sectionMergeSort(dataList, section1, section2);
        int currIndex1 = section1.getStartIndex();
        int endIndex1 = section1.getEndIndex();
        int currIndex2 = section2.getStartIndex();
        int endIndex2 = section2.getEndIndex();
        List<Integer> tempList = new ArrayList<>(
                endIndex1 - currIndex1 +
                        endIndex2 - currIndex2 + 2);


        //将排序好的值再填充会原集合使用到的变量（伪分段导致的）
        int lowerCurrIndex = currIndex1 > currIndex2 ? currIndex2 : currIndex1;
        int biggerCurrIndex = currIndex1 > currIndex2 ? currIndex1 : currIndex2;
        int lowerEndIndex = endIndex1 > endIndex2 ? endIndex2 : endIndex1;
        int biggerEndIndex = endIndex1 > endIndex2 ? endIndex1 : endIndex2;
        int tempCurrIndex = 0;


        for (; currIndex1 <= endIndex1; ) {
            for (; currIndex2 <= endIndex2; ) {
                int currVal1 = dataList.get(currIndex1);
                int currVal2 = dataList.get(currIndex2);
                if (currVal1 <= currVal2) {
                    tempList.add(currVal1);
                    currIndex1++;
                    break;
                }
                if (currVal1 > currVal2) {
                    tempList.add(currVal2);
                    currIndex2++;
                    continue;
                }
            }
            if (currIndex2 > endIndex2) {
                break;
            }
        }

        //修正没有扫描到的索引位置
        // （上面一个for循环与下面的两个for循环，总共将每个索引位置只扫描了一遍）
        //toalScanCount = endIndex1 - currIndex1 + endIndex2 - currIndex2 + 2

        for (; currIndex1 <= endIndex1; currIndex1++) {
            tempList.add(dataList.get(currIndex1));
        }
        for (; currIndex2 <= endIndex2; currIndex2++) {
            tempList.add(dataList.get(currIndex2));
        }


        //将排序好的值再填充会原集合（伪分段导致的，不是伪分段的话直接将tempList返回就行）
        for (; lowerCurrIndex <= lowerEndIndex; lowerCurrIndex++) {
            dataList.set(lowerCurrIndex, tempList.get(tempCurrIndex++));
        }
        for (; biggerCurrIndex <= biggerEndIndex; biggerCurrIndex++) {
            dataList.set(biggerCurrIndex, tempList.get(tempCurrIndex++));
        }

    }

    private void sectionMergeSort(List<Integer> dataList, Section section1, Section section2) {
        if (!section1.isOrder) {
            mergeSort(dataList, section1);
        }
        if (!section2.isOrder) {
            mergeSort(dataList, section2);
        }
    }

    private int getSplitSectionIndex(Section section) {
        //策略例子：采用中位点为分隔点
        return (section.getStartIndex() + section.getEndIndex()) / 2;//向下取整
    }

    private boolean validateSectionIsSpilt(Section section) {
        return section.getStartIndex() != section.getEndIndex();
    }

    /**
     * 段定义，通过段的开始索引，结束索引坐标
     * 实现伪段划分
     */
    private class Section {
        private int startIndex;
        private int endIndex;
        private boolean isOrder;

        public Section(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            isOrder = false;
        }

        public int getStartIndex() {
            return startIndex;
        }

        public void setStartIndex(int startIndex) {
            this.startIndex = startIndex;
        }

        public int getEndIndex() {
            return endIndex;
        }

        public void setEndIndex(int endIndex) {
            this.endIndex = endIndex;
        }

        public boolean isOrder() {
            return isOrder;
        }

        public void setOrder(boolean order) {
            isOrder = order;
        }
    }
}
